use crate::utils::time_cost;
use std::cmp::{max, min, Ordering};
use std::collections::HashMap;
use std::fmt::{Display, Formatter};
use std::ops::Deref;

type NodePtr<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: NodePtr<T>,
}

impl<T: Display> Display for Node<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}->", self.data);
        let mut node_ref = &self.next;
        while let Some(node) = node_ref {
            write!(f, "{}->", node.data);
            if let Some(node) = &node_ref {
                node_ref = &node.next;
            }
        }
        write!(f, "END")
    }
}

impl<T> Node<T> {
    fn new(data: T, next: NodePtr<T>) -> Self {
        Self { data, next }
    }
    fn from_vec(vec: Vec<T>) -> NodePtr<T> {
        let mut head = None;
        for elem in vec.into_iter().rev() {
            let node = Box::new(Node::new(elem, head.take()));
            head.replace(node);
        }
        head
    }
}

fn into_vec<T>(mut head: NodePtr<T>) -> Vec<T> {
    let mut result = Vec::new();
    while let Some(node) = head.take() {
        result.push(node.data);
        head = node.next;
    }
    result
}

fn reverse<T, F>(mut head: Box<Node<T>>, mut f: F) -> Box<Node<T>>
where
    F: FnMut(&mut T),
{
    f(&mut head.data);
    let mut next = head.next.take();
    while let Some(mut node) = next {
        next = node.next.replace(head);
        head = node;
        f(&mut head.data);
    }
    head
}

fn add(a: NodePtr<u32>, b: NodePtr<u32>) -> NodePtr<u32> {
    match (a, b) {
        (Some(a), Some(b)) => {
            let (mut a_len, mut b_len) = (0, 0);
            let a = reverse(a, |_| a_len += 1);
            let b = reverse(b, |_| b_len += 1);
            let (a, b) = if a_len > b_len { (a, b) } else { (b, a) };
            let mut b_ref = Some(b.deref());
            let mut carry = 0;
            let mut head = reverse(a, |digit| {
                if let Some(b) = b_ref {
                    *digit += b.data;
                    b_ref = b.next.as_deref();
                }
                *digit += carry;
                carry = if *digit >= 10 {
                    *digit -= 10;
                    1
                } else {
                    0
                };
            });
            if carry != 0 {
                head = Box::new(Node::new(1, Some(head)));
            }
            Some(head)
        }
        (Some(a), None) | (None, Some(a)) => Some(a),
        (None, None) => None,
    }
}

#[test]
fn test_list() {
    fn test_add(a: Vec<u32>, b: Vec<u32>, expected: Vec<u32>) {
        let a = Node::from_vec(a);
        let b = Node::from_vec(b);
        assert_eq!(into_vec(add(a, b)), expected);
    }
    test_add(vec![1, 2, 3, 4], vec![2, 3, 4], vec![1, 4, 6, 8]);
    test_add(vec![], vec![2, 3, 4], vec![2, 3, 4]);
    test_add(vec![1, 2, 3, 4], vec![], vec![1, 2, 3, 4]);
    test_add(vec![1], vec![], vec![1]);
    test_add(vec![9], vec![1], vec![1, 0]);
    test_add(vec![9, 9, 9, 9], vec![1], vec![1, 0, 0, 0, 0]);
}

#[test]
fn test_1() {
    let mut vec1 = Vec::new();
    for x in 0..1000 {
        vec1.push(x);
    }

    time_cost(|| {
        for _ in 0..100 {
            let vec = vec1.clone();
            reverse(Node::from_vec(vec).unwrap(), |data| {
                print!("{data}->");
            });
        }
    });

    time_cost(|| {
        for _ in 0..100 {
            let vec = vec1.clone();
            println!("{}", Node::from_vec(vec).unwrap());
        }
    });

    // let mut head = Node::from_vec(vec![1, 2, 3]);
    // let reverse_head = reverse(head.unwrap(), |_| {});
    // println!("{:?}", reverse_head);
}

#[test]
pub fn do_test() {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut vec1 = Vec::new();
        vec1.reserve(2);
        if nums.len() < 2 {
            return Vec::new();
        }
        let mut map = std::collections::HashMap::with_capacity(nums.len());
        for x in nums.iter().enumerate() {
            match map.get(&(target - x.1)) {
                None => {
                    map.insert(x.1, x.0);
                }
                Some(e) => {
                    vec1.push(x.0 as i32);
                    vec1.push(*e as i32);
                    return vec1;
                }
            }
        }

        vec1
    }

    pub fn min_taps(n: i32, ranges: Vec<i32>) -> i32 {
        // ranges.iter().enumerate();

        let mut vec: Vec<(i32, i32)> = ranges
            .into_iter()
            .enumerate()
            .map(|(i, e)| (0.max(i as i32 - e), n.min(i as i32 + e)))
            .collect();
        println!("{:?}", vec);
        vec.sort_by(|(a, _), (b, _)| a.cmp(b));

        let mut dp = Vec::new();
        for x in 0..=n + 1 {
            dp.push(i32::MAX);
        }
        dp[0] = 0;
        for (start, end) in vec.into_iter() {
            if dp[start as usize] == i32::MAX {
                return -1;
            }
            for i in start..=end {
                let j = i as usize;
                dp[j] = dp[j].min(1 + dp[start as usize]);
            }
        }

        dp[n as usize]
    }
    println!("{}", min_taps(2, vec![0, 0, 1]));
    println!("{:?}", two_sum(vec![3, 2, 4], 6));
}
